package com.java.comprehensive.arithmetic.leecode.tags.linkedlist;

import util.ListNode;

/**
 * @Author: 窦绍飞
 * @Date: 2022/7/3
 */
public class LeetCode_19 {
	static int count = 0;

	public static ListNode removeNthFromEnd(ListNode head, int n) {
		if (head == null)
			return null;
		head.next = removeNthFromEnd(head.next, n);
		count++;
		if (count == n) {
			return head.next;
		}
		return head;
	}

	// 这样双指针其实就是直接 通过快指针找到了 把倒着第几个被删除链，变成了正着数第第几个然后直接删除，不用反转了
	public static ListNode removeNthFromEndTwo(ListNode head, int n) {

		if (head == null || head.next == null)
			return null;

		ListNode fast = head, slow = head;
		for (int i = 1; i <= n; i++) {
			fast = fast.next;
		}
		if (fast == null)
			return head.next;
		while (fast.next != null) {
			fast = fast.next;
			slow = slow.next;
		}
		slow.next = slow.next.next;
		return head;
	}

	public static ListNode removeNthFromEndThree(ListNode head, int n) {

		if (head == null || head.next == null)
			return null;
		ListNode slow = head;
		int count = 0;
		while (slow.next != null) {
			if (count == n) {
				slow.next = slow.next.next;
			}
			slow = slow.next;
			count++;
		}
		return head;
	}

	// 先反转
	private static ListNode reversal(ListNode head) {
		// 直线反转好的第一个节点
		ListNode pre = null;
		ListNode curr = head;
		while (curr != null) {
			ListNode node = curr.next;
			curr.next = pre;
			pre = curr;
			curr = node;
		}
		return pre;
	}

	public static ListNode removeNthFromEnd_January_29_2023(ListNode head, int n) {

		ListNode tempFast = head;
		ListNode tempLow = head;

		for (int i = 0; i < n; i++) {
			tempFast = tempFast.next;
		}
		if (tempFast == null) {
			return head.next;
		}
		while (tempFast.next != null) {
			tempFast = tempFast.next;
			tempLow = tempLow.next;
		}
		tempLow.next = tempLow.next.next;

		return head;
	}

	public static void main(String[] args) {
		ListNode listNode8 = new ListNode(5, null);
		ListNode listNode4 = new ListNode(4, listNode8);
		ListNode listNode5 = new ListNode(3, listNode4);
		ListNode listNode6 = new ListNode(2, listNode5);
		ListNode listNode7 = new ListNode(1, listNode6);
		ListNode listNode = removeNthFromEnd_January_29_2023(listNode7, 2);
		System.out.println(listNode);
	}
}
